program XI182009_3aDYBZOCfnc_zero;
uses crt;

{
18 XI 2009r. written by Piotr D. & Artur Z.
Dobra, mamy tu jakies cuda, wianki na kiju, ale co tu sie tak naprawde stalo?
mamy takie funkcje:
	function f(x:real):real;
		funkcja ta oblicza wartosc funkcji, uzywane do sprawdzania, czy wartosci na poczatku i koncu przeszukiwanego
                przdzialu sa roznego znaku
	function isZero(a,b:real):boolean;
		zwraca wartosc logiczna,
		sprawdza, czy w przedziale <a, b> jest miejsce zerowe, tj. czy f(a)*f(b)<0
	function getZeroFromRecursive(a,b:real):real;
		zwraca mniejsce zerowe obliczone rekurencyjnie wystepujace w przedziale <a,b>, nie jest wskazane korzystanie z niej,
                jesli nie jestsmy pewni, ze w <a,b> jest miejsce zerowe, inaczej: musimy sprawdzic isZero() najpierw, czy jest
	function getZeroFromIterative(a,b:real):real;
		podobne do getZeroFromRecursive, lecz, jak sama nazwa wskazuje, oblicza iteracyjnie. w wielu przypadkach iteracyjnie
                liczymy szybiej, niz rekurencyjnie, iteracyjnie zapobiegamy rowniez 'przepelnieniu stosu'

}

var pa,pb,l,zmiana:real;  cntlines:integer;    znaleziono,tmp:boolean;     czyChcemy,wyswietlajDzialanieFunkcji:char;
SKOK:REAL;
label start; {taki tam dodatek, na koncu jest pytanie, czy chcemy zakonczyc prace z programem, ogolnie moznaby to wywalic}

procedure writelm(line:string;is:boolean);
begin
 inc(cntlines);
 if (cntlines=21) and (cntlines<25) and (wyswietlajDzialanieFunkcji='t') then
 begin
  cntlines:=0;
  textcolor(lightgray);
  textbackground(black);
  write('Ta linijka pomaga w analizowaniu,');
  textcolor(white);
  writeln(' aby wylaczyc wcisnij Q, INNT KLAWISZ=dalej.');
  textbackground(black);
  textcolor(lightgray);
  if readkey in ['q','Q'] then cntlines:=25;
 end;
 write(line);
 if is then writeln;
end;

function f(x:real):real;
	{
	najprostrza funkcja, z ktorymi stykamy sie na lekcjach matematyki
	}
	begin
             f:=0*x*x*x*x*x+2*x*x*x*x-3*x*x*x+5*x*x+7*x-12;
	end;

function isZero(a,b:real):boolean;
	{
	argumenty funkcji:
	a-pierwsza wartosc okreslajaca przedzial
	b-druga wartosc okreslajaca przedzial

	wartosc funkcji:
	typ logiczny - tak, jesli w tym przdziale jest miejsce zerowe, falsz - jesli nie ma.
	}
	var p,d:boolean;
	begin
		if f(a)<=0 then p:=true else p:=false;
		if f(b)<=0 then d:=true else d:=false;
			isZero:= p=not d;
		{to jest oczywiscie rownowazne z sprawdzaniem, czy f(a)*f(b)<0, ale dlaczego to jest lepsze? zalozmy, ze maxymalny rozmiar
		real to 10^6, a f(a)=~(-f(b)),
		co sie stanie, jesli pomnozymy ~10^6*10^6? w algorytmice efekt bedzie porownywalne z dzieleniem przez 0. 10^12
		nie zmiesci sie w pamieci, wiec wywali blad, porownywanie znakow obu wartosci jest rozsadniejsze}
	end;

function getZeroFromRecursive(a,b:real):real;
	var c:real;
	begin
		c:=(a+b)/2;
		if wyswietlajDzialanieFunkcji='t' then begin textcolor(lightgray);writelm('Obserwujemy f. rekurencyjna: x/in<',false);
                write(a:4:4);write('; '); write(b:4:4); write('> srodek: ');
                write(c:4:4);writeln; end; {ta linijka to taki bajer}
		if (abs(a-b)<0.00001) then
			getZeroFromRecursive:=a
			else if (isZero(a,c)) then
				getZeroFromRecursive:=getZeroFromRecursive(a,c)
				else if (isZero(c,b)) then getZeroFromRecursive:=getZeroFromRecursive(c,b)
					else exit; {teoreycznie przypadek nieosiagalny, ale you never know, wiec lepiej zabic proces, ta linijke mozecie pominac
					(ofc. pamietajac o sredniku xDDDDDDDD)}
	end;

function getZeroFromIterative(a,b:real):real;
	var c:real;
	begin
		repeat
		c:=(a+b)/2;
		if wyswietlajDzialanieFunkcji='t' then begin textcolor(lightgray);writelm('Obserwujemy f. iteracyjna: x/in<',false);
                write(a:4:4);write('; '); write(b:4:4); write('> srodek: ');  write(c:4:4);writeln;end;{ta linia to taki bajer}
		if isZero(a,c) then b:=c
		   else if isZero(c,b) then a:=c
			else exit; {jak w rekurencyjnej, nie chcemy, aby jakis blad sie wdal, dlatego lepiej zrobic zakonczenie programu,
				   to lepsze, niz swiadome pozwolenie na blad}
		until abs(a-b)<0.00001; {ta stala to dopuszczalny blad}
		getZeroFromIterative:=a; {lub (a+b)/2, po, to zeby zmniejszyc mozliwy blad, ale nie gwarantuje to 100% optymalizacji,
					 wiec olac to chwilowo}
	end;

begin
{//clrscr;}
cntlines:=0;
textcolor(lightmagenta);
textbackground(black);
{a co ;d}  writelm('  START ',true);
textcolor(lightgray);
textbackground(black);
           writelm('  W funkcjach jest mozliwosc obserwowania tego co i jak obliczaja funkcje.',true);
           writelm('Te informacje maja byc wyswietlane? [t/y/T/Y=tak, n,N=nie]',true);
           readln(wyswietlajDzialanieFunkcji);
           if wyswietlajDzialanieFunkcji in ['T','Y','y'] then wyswietlajDzialanieFunkcji:='t';
start:     writelm('  Podaj przedzial, poczatek i koniec oddziel entersem lub wdus np. q, zeby',true);
           writelm('wywolac blad=>zakonczenie programu, cute, isn''t it?',true);
           {specjalnie napisalem isn't it po to, zeby pochwalic sie, ze wiem jak wypisac
           apostrof w pascalu, fachowo to sie nazywa character escaping

           {repeat {pozniej usunalem rownez sprawdzanie, czy w podanym przedziale istnieje miejsce zerowe, linia~113}
                 readln(pa,pb); {2 argumenty dlatego, ze mozna wczytywac 2 w jednej linii}

           {nie chcielibysmy, aby pa>pb, dlatego w razie potrzebny zamienmy je}
           if pa>pb then
              begin
              zmiana:=pa;
              pa:=pb;
              pb:=zmiana;
              end;

	{modyfikowany fragment kodu specyficzny dla FUNKCJI KWADRATOWEJ START}
	{fragmenty, ktore dodalem po napisaniu obslugi liniowej pisze WIELKIMI LITERAMI}
		{Moze troche o samej metodzie, jesli ktos nie sluchal na lekcji albo po prostu lubi czytac text w dosie (ewentualnie innym
                edytorze textu z czcionka TrueType -> look wiki)
		Bedziemy sprawdzac o podany krok zmiany, mozemy go jeszcze nazywac delta, okresem, skokiem, przesunieciem przeszukiwanego
                obszaru lub zmiana zbioru aktualnie przeszukiwanych argumentow
		wyobrazcie sobie, ze os OX na wykresie dzielimy na cos pododnego do asymptot (tylko na wykresie, nie w teorii),
		asymptoty rysujemy dokladnie tak, zeby utworzyly one jakies tam podzbiory,
		cale zadanie polega na tym, ze bedziemy sprawdzac od i-tej asymptoty do (i+1)-tej asymptoty, czy wsrod tych liczb jest
                jakies miejsce zerowe
			wtracenie: zapewne domyslacie sie, ze jest pewna szansa, ze to popelni blad - well, nie podoba mi sie to,
                        wg mnie powinnismy tutaj wykorzystac pochodna z f(x) i zamiast od i do (i+1) asymptoty przeszukiwac
                        przedzialy, w ktorych pochodna f(x) ma miejsca zerowe
		zrobimy to w ten sposob:
			1. zacznij od a,
			2. wykorzystaj funkcje funkcje isZero do sprawdzenia, czy w danym przedziale jest miejsce zerowe,
                           jako argumenty funkcji podajemy (a, a+okres), dlaczego nie zmieniamy b? przyda to sie pozniej, do
                           koncowego etapu
				2a. jesli znaleziono miejsce zerowe, to je oblicz, wykorzystujac fragment dla fukncji liniowej, z tym, ze teraz obszarem
                                    nie jest zbior podany przez uzytkownika, tylko przedzial wyznaczony
                                    przez nasz algorytm, tj. <a, a+skok>
				2b. jesli nie znaleziono, to idz do kolejnego sprawdzenia przedzialu
			X. <wariant, ktory powinien byc na poczatku, ale wole go umiescic na koncu, bo moze ktos poczatek ominie szybciej xD>
			   co, jesli a+skok>b podanego przez usera (b, ktorego nie modyfikowalismy na poczatku - punkt 1.)? Nie powinnismy wyjsc
                           poza zbior podany przez uzytkownika, dlatego wstawmy fragment wyznaczajacy minimum z 2 wartosci,
                           czyli if a+skok>b then a:=b else a:=a+skok
			=>punkty 1-X powtarzamy do czasu, az a+skok>=b (kolejne sprawdzenie spowodowaloby wyjscie poza zbior podany przez usera)
			Uwagi: w moim kodzie ap odpowiada a z opisu, a ap odpowiada b z opisu.
		}
                 znaleziono:=false;
                 SKOK:=0.01;
		 WHILE PA+SKOK<=PB DO
                 BEGIN

                   {usuniete w kwadratowej, bo troche trzeba dopisac szczegolow, zeby dzialalo z podprzedzialami
		    if not tmp then
		     writelm('nie znaleziono miejsca zerowego, ponow wpisanie przedzialu: ');
		   until tmp;}
		   IF ISZERO(PA,PA+SKOK) THEN
			BEGIN
				l:=getZeroFromRecursive(pa,PA+SKOK);{W LINIOWEJ BYLO l:=getZeroFromRecursive(pa,pb);}
textcolor(white);	        writelm('znaleziono, rekurencyjnie, f(x)~=0 dla x=',false); write(l:4:4); writeln;
				l:=getZeroFromIterative(pa,PA+SKOK);{W LINIOWEJ BYLO l:=getZeroFromIterative(pa,pb);}
textcolor(white);               writelm('znaleziono, iteracyjnie, f(x)~=0 dla x=',false); write(l:4:4); writeln;
                                ZNALEZIONO:=true;
			END;
textcolor(lightgray);
                   PA:=PA+SKOK;
                   IF PA>PB THEN PA:=PB;
		 END;
textcolor(lightgray);
                 IF NOT ZNALEZIONO THEN writelm('Jest duze prawdopodobienstwo, ze ta funkcja nie ma miejsc zerowych',true);
	{KWADRATOWEJ FUNKCJI dla specyficzny kodu fragment modyfikowany END}
{teoretycznie tutaj konczy sie to, co mielismy zrobic na lekcji, to 1. zadanie}
           writelm('Czy zakoczono prace z programem? [t|y /n]',true);
           readln(czyChcemy);
if czyChcemy in['n','N'] then
   goto start; {wykorzystanie etykiet, w pewnych momentach sa czytelniejsze,
ale w pisaniu algorytmu sa wrecz mocno odradzane xd}


end.